package 动态规划;

public class No309最佳买卖股票时机含冷冻期 {

    /**
     * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     *
     * 示例:
     * 输入: [1,2,3,0,2]
     * 输出: 3
     * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     */

    /**
     * 用动态规划求解,求前1天的最大利润
     * 条件一:只能有一笔交易;条件二:卖出后第二天不能买
     * 假设:[1,2,3,0,2]
     * 想法:只用兼顾两者:今天,明天;明天跌,就卖出;未拥有时就判断第二天是否会涨,然后买入
     * 先用普通for写一下
     * 写完后发现不可以只兼顾当前利润的情况,因为假设一个例子:[1,2,3,0,2]
     * 最大应该是[(2-1)+(2-0)=3],但是只兼顾今天和明天就会(3-1)=2,结果出错。
     * 正确姿势应该是每天都买,然后预测后面的情况,二维dp数组;
     * 参考weiwei哥   dp[i][j]->第i天,状态j,拥有的利润;状态:0无持股,1当天持股,2当天卖出
     */
    public int maxProfit(int[] prices) {

        if(prices.length<2){
            return 0;
        }

        int[][] dp=new int[prices.length+1][3];
        dp[0][0]=0;//无股
        dp[0][1]=-prices[0];//买入
        dp[0][2]=0;//卖出,但并没持股,所以为0

        for (int i = 1; i < prices.length; i++) {
            //dp[]数组存的是当前金额
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);//无股:max(昨天无股,昨天卖出)
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);//持股:max(昨天持股,今天买入)
            dp[i][2]=dp[i-1][1]+prices[i];//卖出:max(昨天有股今天卖出)
        }

        //最后一天卖出或最后一天无股
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][2]);
    }

    public static void main(String[] args) {
        No309最佳买卖股票时机含冷冻期 n=new No309最佳买卖股票时机含冷冻期();
        int[] arr={1,2,3,0,2};
        int result = n.maxProfit(arr);
        System.out.println(result);
    }

}
